package com.fanpan26.algo.sort;

import java.util.Arrays;

/**
 * @author fanpan26
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8,};

        //quickSort(arr,0,arr.length -1);
        //System.out.println(Arrays.toString(arr));

        System.out.println(getRankNumber(arr,0,arr.length-1,5)+"??23");
    }

    private static void quickSort(int[] arr,int low,int high) {
        int index = getIndex(arr, low, high);

        if (low < high) {
            quickSort(arr, 0, index);
            quickSort(arr, index + 1, high);
        }
    }

    private static int getRankNumber(int[] arr,int low,int high,int no){
        int index =getIndex(arr,low,high);

        System.out.println(Arrays.toString(arr));

        //如果恰好找到，返回
        if (index +1 == no){
            return arr[index];
            //如果索引小于 ，在右边
        }else if(index+1< no){
           return getRankNumber(arr,index+1,high,no);
        }else{
            //在左边
           return getRankNumber(arr,0,index,no);
        }
    }


    private static int getIndex(int[] arr,int low,int high){
        int value = arr[low];

        while (low<high){
            while (low<high && arr[high]>value){
                high --;
            }
            arr[low] = arr[high];
            while (low<high && arr[low]<value){
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = value;

        return low;

    }
}